1. Field of the Invention
This invention relates generally to non-volatile memory, and more particularly to providing high speed cache flushing in a non-volatile memory.
2. Description of the Related Art
Today, data processing systems often reduce memory access time through the use of cache memory. Cache memory generally is a small high speed memory utilized to temporarily replicate portions of main memory that are frequently accessed. As a result, the average memory access time is reduced because most memory access is to the cache memory, which generally is faster than main memory. Thus, software executing on the system generally executes faster because most software tends to access the same portions of memory many times. Hence, the system is able to perform fewer memory accesses to slower main memory when the frequently accessed data is stored in cache.
In general, each memory access request is passed to a cache controller, which tracks which portions of main memory are currently stored in cache memory. If a memory access request (i.e., read request or write request) is made to data currently stored in cache memory, a “cache hit” occurs and the cache memory is utilized to complete the memory access request. However, if the memory access request is made to data not currently stored in cache memory, a “cache miss” occurs, and the data is accessed from main memory. In some systems, when a miss occurs, the cache controller can assign the requested miss address to the cache memory and fetch the data from main memory to store in the cache memory.
While cache memory is useful during memory access, problems can occur during sudden losses in power. When the system detects a pending power problem, the system generally needs to prepare itself for the power loss by flushing the cache memory. This can also occur at other times, such as when the system prepares to power down. Cache flushing refers to the method by which a system writes the data currently stored in cache memory back to main memory. That is, when the system prepares to shut down or detects a pending power problem, the system generates a flush cache command. In response, the data stored in the cache memory is written to the corresponding addresses in main memory. The flush cache process is generally straight forward in terms of volatile memory; however, the process is more complex when using non-volatile memory.
Non-volatile memory is memory that stores data when power is disconnected from the system. Phase-change memory (PCM) and flash memory are examples of non-volatile computer memory. Flash memory is a non-volatile computer memory that can be electrically erased and reprogrammed. Because flash memory retains stored data even when power to the memory is turned off, flash memory is widely used in battery-portable devices. For example, flash memory often is utilized in digital audio players, digital cameras, mobile phones, and USB flash drives, which are used for general storage and transfer of data between computers.
FIG. 1 is an illustration showing a typical prior art non-volatile memory arrangement. As illustrated in FIG. 1, a non-volatile memory 100 generally comprises a plurality of memory blocks 102, which generally is the smallest portion of memory that can be erased. Each memory block 102 generally comprises a fixed plurality of pages 104, which is the smallest size element that can be written or read from the non-volatile memory 100.
Unlike many other storage devices, non-volatile memory devices generally cannot be overwritten. Instead, to update data in a particular storage location within non-volatile memory, the location must first be erased, then the new data written in its place. Moreover, when erasing data in a flash device, an entire block must be erased instead of just the particular page or pages of the block that were updated. To facilitate this process, a typical flash controller will find a block of memory that has been previously erased and write the updated page to this new block at the same page offset. Then, the remaining pages of the old block are copied to the new block. Later, the old block is erased and made available for use by some other operation. Thus, when performing a flush cache command, the system generally is required to find free memory for the data stored in cache memory prior to flushing the cache memory.
FIG. 2 is a flowchart showing a prior art method 200 for flushing cache when utilizing a non-volatile memory for data storage. In an initial operation 202, preprocess operations are performed. Preprocess operations can include, for example, detecting a pending power loss, receiving a low power mode request, and other preprocess operations that will be apparent to those skilled in the art.
In a search operation 204, the non-volatile memory is searched for a free memory block. After receiving a flush cache command, the non-volatile memory is searched to find a free memory block for each cache block in cache memory. A free memory block is a memory block that is a good memory block (i.e., not damaged or worn out), not currently storing data, and has been erased. This search can be performed by searching the actual memory array, or by searching, for example, a table storing data regarding the current contents of the non-volatile memory array.
A decision is then made as to whether a free memory block currently exists in the non-volatile memory, in operation 206. If a free memory block currently exists in the non-volatile memory, the method 200 continues to operation 210. Otherwise, the method 200 branches to operation 208.
When the non-volatile memory does not currently include a free memory block, an old memory is erased to enable the cache data to be written in its place, in operation 208. As mentioned above, non-volatile memory generally cannot be overwritten. Thus, if a free memory block does not currently exist in the non-volatile memory, memory needs to be freed up to make room for the cache data. When data is no longer being used in non-volatile memory, the memory block storing the data is marked as storing old data. Generally, the memory block is erased during idle periods. However, it is possible that old data will be present in the non-volatile memory at the time a flush cache command is issued. When this occurs, the memory block storing the old data is erased to enable the memory block to be used to store cache data.
If a free memory block currently exists in the non-volatile memory, or after a memory block storing old data has been erased in operation 208, the cache block is written to the free block in non-volatile memory, in operation 210. Cached data for non-volatile memory often is stored as a cache block in cache memory. Each cache block corresponds to a memory block in non-volatile memory. Thus, during operation 210, the current cache block is written to non-volatile memory.
Another decision is then made as to whether more cache blocks need to be written to non-volatile memory, in operation 212. If more cache blocks need to be written to non-volatile memory, the method 200 continues with another search operation 204. Otherwise, the method 200 completes in operation 214. Then, in operation 214, post process operations are performed. Post process operations can include system shutdown, and other post process operations that will be apparent to those skilled in the art.
Unfortunately, searching for free memory blocks and erasing old memory blocks can take considerable time, depending on the size of the cache memory and the amount of non-volatile memory data cached. For example, the worst case scenario is represented by equation 1 below:N*(T1+T2)   (1)
where N is the number of cache blocks, T1 is the erase time for a memory block, and T2 is the program/write time for a memory block. In typical prior art systems, this can take in the range of about N*20 Msecs, which is a relatively long time particularly when a power loss is pending.
In view of the foregoing, there is a need for systems and methods for providing high speed cache flushing in a non-volatile memory. The systems and methods should decrease the amount of time required to complete a flush cache command. In addition, the systems and methods should not unduly burden the system or have prohibitive costs associated with them.